In
automata theory
Automata theory is the study of abstract machines and automata, as well as the computational problems that can be solved using them. It is a theory in theoretical computer science. The word ''automata'' comes from the Greek word αὐτόματο ...
, an alternating tree automaton (ATA) is an extension of
nondeterministic tree automaton as same as
alternating finite automaton In automata theory, an alternating finite automaton (AFA) is a nondeterministic finite automaton whose transitions are divided into ''existential'' and ''universal'' transitions. For example, let ''A'' be an alternating automaton.
* For an existenti ...
extends
nondeterministic finite automaton
In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if
* each of its transitions is ''uniquely'' determined by its source state and input symbol, and
* reading an input symbol is required for each state tr ...
(NFA).
Computational complexity
The emptiness problem (deciding whether the language of an input ATA is empty) and the universality problem for ATAs are
EXPTIME-complete
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that are solvable by a deterministic Turing machine in exponential time, i.e., in O(2''p''(''n'')) time, w ...
.
[H. Comon, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison et M. Tommasi, ''Tree Automata Techniques and Applications']
(Theorem 7.5.1 and subsequent remark) The membership problem (testing whether an input tree is accepted by an input AFA) is in PTIME.
References
Automata (computation)
{{comp-sci-theory-stub